package com.zwj.interview.动态规划;

/**
 * 题目：
 * 输入字符串S和T，请计算字符串S中有多少个子序列等于字符串T。例如,在字符串"appplep"中，有3个子序列等于字符串"apple"
 */
public class ST子序列个数 {

    /**
     * 分析：
     * <p>
     * 由于这个问题的输入有两个字符串，因此状态转移方程有两个参数。
     * 用f(i,j)表示字符串S下标从0到i的子字符串（记为S[0..i]）中等于字符串T下标从0到j的子字符串（记为T[0..j]）的子序列的数目。
     * 如果字符串S的长度是m，字符串T的长度是n，那么f（m-1，n-1）就是字符串S中等于字符串T的子序列的数目
     * 定义dp[i,j]来表示结果
     * <p>
     * 当字符串S的长度小于字符串T的长度时，字符串S中不可能存在等于字符串T的子序列，所以当i小于j时f（i，j）的值都等于0
     * <p>
     * 如果字符串S中下标为i的字符（记为S[i]）等于字符串T中下标为j的字符（记为T[j]），
     * 那么对S[i]有两个选择：
     * 一个是用S[i]去匹配T[j]，那么S[0..i]中等于T[0..j]的子序列的数目等于S[0..i-1]中等于T[0..j-1]的子序列的数目；
     * 另一个是舍去S[i]，那么S[0..i]中等于T[0..j]的子序列的数目等于S[0..i-1]中等于T[0..j]的子序列的数目。
     * 因此，当S[i]等于T[j]时，f（i，j）等于f（i-1，j-1）+f（i-1，j）
     * <p>
     * 如果S[i]和T[j]不相同，则只能舍去S[i]，此时f（i，j）等于f（i-1，j）
     * <p>
     * 接着考虑字符串S和T为空的情形。由于f（0，j）表示S[0..0]（子字符串的长度为1）中等于T[0..j]的子序列的数目，
     * 因此f（-1，j）表示字符串S为空。同理，f（i，-1）表示字符串T为空
     * <p>
     * 当字符串S、T都为空时，两个字符串匹配，因此f（-1，-1）等于1。如果字符串S为空而字符串T不为空，
     * 那么字符串S中不可能存在等于字符串T的子序列，即当j大于或等于0时f（-1，j）等于0。
     */

    public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        //base case 当s和t都为空的时候，那么结果为1
        dp[0][0] = 1;
        for (int i = 0; i < s.length(); i++) {
            /**
             * 如果字符串S不为空而字符串T为空，那么字符串S的空子序列（舍去字符串S的所有字符）等于字符串T，
             * 即当i大于或等于0时f（i，-1）等于1
             */
            //特殊情况
            dp[i + 1][0] = 1;
            for (int j = 0; j <= i && j < t.length(); j++) {
                /**
                 * 如果字符串S的长度为m，字符串T的长度为n，则上述代码中二维数组dp的行数为m+1，
                 * 列数为n+1。f（i，j）的值保存在“dp[i+1][j+1]”中。
                 * 代码中的二重循环根据S[i]和T[j]是否相同按照状态转移方程计算f（i，j）
                 */
                if (s.charAt(i) == t.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
                } else {
                    dp[i + 1][j + 1] = dp[i][j + 1];
                }
            }


        }
        return dp[s.length()][t.length()];
    }
}
